//https://leetcode.cn/problems/number-of-provinces/submissions/583034932/

class Solution {
private:
    int father[210]; // 并查集的父节点数组，题目限制 1 <= n <= 200
    int n; // 节点数量（城市数量）

    // 并查集初始化，每个节点的父节点初始为自己
    void init() {
        for (int i = 0; i < n; ++i) {
            father[i] = i;
        }
    }

    // 并查集的查找操作，路径压缩优化
    // 找到节点 u 所在集合的根节点
    int find(int u) {
        // 如果 u 是自己的父节点，说明 u 是根节点；否则递归查找父节点并路径压缩
        return u == father[u] ? u : father[u] = find(father[u]);
    }

    // 并查集的合并操作，将节点 v 所属的集合合并到节点 u 所属的集合
    void join(int u, int v) {
        u = find(u); // 找到 u 的根节点
        v = find(v); // 找到 v 的根节点
        if (u != v) {
            father[v] = u; // 将 v 的根指向 u 的根
        }
    }

    // 判断两个节点 u 和 v 是否属于同一个集合（此题未用到该方法）
    bool same(int u, int v) {
        return find(u) == find(v);
    }

public:
    // 主函数：计算省份数量（连通子图的数量）
    int findCircleNum(vector<vector<int>>& isConnected) {
        n = isConnected.size(); // 获取城市数量
        init(); // 初始化并查集

        // 遍历邻接矩阵，合并相连的城市
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) { // 遍历上三角矩阵，避免重复判断
                if (isConnected[i][j]) {
                    join(i, j); // 合并两个相连的城市
                }
            }
        }

        // 统计最终连通子图的数量
        unordered_set<int> uset; // 使用集合存储每个集合的根节点
        for (int i = 0; i < n; i++) {
            uset.insert(find(i)); // 查找每个节点的根，并插入集合
        }
        return uset.size(); // 集合的大小即为连通子图的数量
    }
};
